home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 090 / cmln0485.arc / CROSTH1.LTG < prev    next >
Text File  |  1986-02-27  |  3KB  |  99 lines
  1. crosstht. Listing 1.  
  2.  
  3.  
  4.  
  5.  
  6. ┴ collectioε oµ procedures¼ writteε iε PPL¼ fo≥ initializing¼ ì
  7. addinτ, anΣ searchinτ fo≥ records
  8.  
  9. -- Data types will be defined in a Pascal-like style.
  10.  
  11. -- RECORD : Anytype;
  12. -- KeyData : record Key : Anytype; RecordPointer : integer end;
  13. -- Map : array[1..MAXROW,1..MAXROW] of record  First, Last : integer  end;
  14. -- Cell : record  First, Last : integer  end;
  15. -- Bucket : record
  16. --            NumSlot, PreviousBucket, NextBucket : Integer;
  17. --            Slots : array[1..BUCKETSIZE] of (same type as) KeyData
  18. --          end;
  19.  
  20. PROCEDURE Initialize
  21.  
  22. OPEN "DATAFILE",1,"RANDOM"
  23. OPEN "KEYFILE",2,"RANDOM"
  24. NData = 0; NBucket = 0;
  25. Zero all elements of Map
  26.  
  27. END Initialize
  28.  
  29.  
  30. PROCEDURE Add
  31.  
  32. Obtain RECORD
  33. NData += 1; KeyData.RecordPointer = NData;
  34. WRITE 1, RECORD
  35. Row = Hash1(KeyData.Key); Column = Hash2(KeyData.Key)
  36. Cell = Map[Row,Column]
  37. IF Cell.First = 0 
  38. THEN -- create a new bucket
  39.    [Add_to_New_Bucket]
  40.    Map[Row,Column].First = NBucket; Map[Row,Column].Last = NBucket;
  41. ELSE -- Locate last bucket
  42.    READ 2, Cell.Last, Bucket
  43.    IF Bucket.NumSlot = BUCKETSIZE  -- Is the bucket full?
  44.    THEN -- Create a new bucket and maintain linked list
  45.       Bucket.NextBucket = NBucket + 1; WRITE 2, Cell.Last,Bucket
  46.       [Add_to_New_Bucket]
  47.       Map[Row,Column].Last = NBucket -- keep track of last bucket in list
  48.    ELSE -- Add in the same bucket
  49.       Bucket.NumSlot += 1
  50.       Bucket.Slots[Bucket.NumSlot] = KeyData
  51.       WRITE 2, Cell.Last,Bucket
  52.    END IF;
  53. END IF;                  
  54.  
  55. èPROCEDURE Add_to_New_Bucket
  56.  
  57. NBucket += 1; Bucket.NumSlot = 1; 
  58. Bucket.PreviousBucket = Cell.Last -- pointer to previous bucket or zero if
  59.                                   -- this is the first bucket in the list
  60. Bucket.NextBucket = 0 -- zero indicates end of linked list.
  61. Bucket.Slots[1] = KeyData
  62. WRITE 2, NBucket, Bucket     
  63.  
  64. END Add_to_New_Bucket
  65.  
  66.  
  67. PROCEDURE Search;
  68. -- Seacrh through buckets.
  69. Obtain SearchKey
  70. Row = Hash1(SearchKey); Column = Hash2(SearchKey)
  71. Cell = Map[Row,Column]
  72. IF Cell.First = 0 -- sought data is definitely not on file
  73. THEN
  74.    DISPLAY "Data nonexistent"
  75. ELSE
  76.    INITIALIZE: FoundFlag = False; NextOne = Cell.First
  77.    LOOP <BIG>
  78.    BEGIN
  79.      READ 2, NextOne, Bucket
  80.      INITIALIZE: None
  81.      LOOP <Look_in_a_Bucket>
  82.      BEGIN for i = 1 to NumSlot
  83.        IF Slots[i].Key = SearchKey THEN FoundFlag = True; EXIT <BIG> END IF;
  84.      END LOOP <Look_in_a_Bucket>;
  85.      TERMINATE: NextOne = Bucket.NextBucket
  86.      IF  NextOne = 0 THEN EXIT <BIG> END IF;  -- when end of link is  found
  87.                                               -- exit loop
  88.    END LOOP <BIG>;
  89.    TERMINATE: IF FoundFlag 
  90.               THEN 
  91.                  DISPLAY "Data in record # ";Slot[i].RecordPointer
  92.                  READ 1, Slot[i].RecordPointer, RECORD
  93.                  -- Perform more data processing of your choice
  94.               ELSE
  95.                  DISPLAY "Data nonexistent"
  96.               END IF;
  97.  
  98. END Search
  99.